Traditionally, computer programs operate in single-threaded computing environments. A single-threaded computing environment means that only one task can operate within the computing environment at a given time. A single-threaded computing environment constrains both users and computer programs. For example, in a single-threaded computing environment, a user is able to run only one computer program at a time. Similarly, in a single-threaded computing environment, a computer program is able to run only one task at a time.
To overcome the limitations of single-threaded computing environments, multi-threaded computing environments have been developed. In a multi-threaded computing environment, a user typically is able to run more than one computer program at a time. For example, a user can simultaneously run both a word processing program and a spreadsheet program. Similarly, in a multi-threaded computing environment, a computer program is usually able to run multiple threads or tasks concurrently. For example, a spreadsheet program can calculate a complex formula that may take minutes to complete while concurrently permitting a user to still continue editing a spreadsheet.
In a multi-threaded computing environment, one or more threads (“update threads”) may need to update a shared data structure. For example, a thread may set or clear timers in a shared timer queue data structure. Conventionally, two approaches—locking the data structure, and sending update requests to a single thread that owns the data structure—are used to synchronize access to the data structure. Locking the data structure requires update threads to wait on a lock of the data structure, which limits the scalability of the system. To send a request to a thread that owns the data structure, two approaches have conventionally been used: allocating a per-request block of memory, and blocking lock acquisition that locks the requested object in a data structure to prevent concurrent access to the requested object by both an update thread and a thread owning the data structure. Both approaches require the use of locks and each approach has its limitations.
The memory allocation approach is slow and prone to failure in low-resource scenarios. Conventionally, a block of memory is allocated for each request to update an object. Memory allocation for a request is slow because a lock is usually required to allocate memory. The memory allocation approach can also fail, for example, for lack of memory. Yet a request as fundamental as to update a timer should not fail for lack of memory.
The blocking lock acquisition approach limits the scalability and performance of a computing system. The blocking lock acquisition approach utilizes the lock associated with a data structure containing objects that multiple threads may request to update. Such a data structure may be a queue. A thread wishing to update an object in the data structure acquires the lock associated with the data structure and updates the object. Upon completing the updating, the thread releases the lock so another thread can acquire the lock and update the same or a different object in the data structure. The blocking lock acquisition approach serializes multiple threads' access to objects in the data structure, thus impairing a computing system's scalability and performance. For example, when multiple threads request to update objects in the data structure, a backlog can be induced. The backlog consists of threads waiting on the lock to be released before they can acquire the lock and proceed to update objects of interest in the data structure. These threads cannot do anything else until they have completed updating their objects of interest in the data structure. Such a backlog thus impairs system performance.
Therefore, there exists a need to update objects in a multi-threaded computing environment without using memory allocations or blocking lock acquisitions, so to avoid the limitations brought by using either of the two approaches.